#include "topoArray.cpp"

typedef struct {
	int v1, v2;
	Weight key;
}Edge;

bool CriticalPath(ALGraph& G, Edge cp[], int& n)
{
	int vex[maxVertices];
	int m;
	if (!(TopologicalSort(G, vex, m)))
	{
		return false;
	}
	EdgeNode* p;
	Weight Ve[maxVertices], Vl[maxVertices];
	Weight Ae[maxVertices], Al[maxVertices];
	for (int i = 0; i < G.numVertices; i++)
	{
		Ve[i] = 0;
	}
	for (int i = 0; i < G.numVertices; i++)
	{
		int u = vex[i];
		for (p = G.VerticesList[u].adj; p != NULL; p = p->link)
		{
			Weight dut = p->cost;
			int v = p->dest;
			if (Ve[u] + dut > Ve[v])
			{
				Ve[v] = Ve[u] + dut;
			}
		}
	}

	for (int i = 0; i < G.numVertices; i++)
	{
		Vl[vex[i]] = Ve[vex[G.numVertices - 1]];
	}
	for (int i = G.numVertices - 2; i >= 0; i--)
	{
		int u = vex[i];
		for (p = G.VerticesList[u].adj; p != NULL; p = p->link)
		{
			int v = p->dest;
			Weight dut = p->cost;
			if (Vl[v] - dut < Vl[u])
			{
				Vl[u] = Vl[v] - dut;
			}
		}
	}

	int k = 0;
	Edge ed;
	for (int i = 0; i < G.numVertices; i++)
	{
		for (p = G.VerticesList[i].adj; p != NULL; p = p->link)
		{
			Ae[k] = Ve[i];
			Al[k] = Vl[p->dest] - p->cost;
			ed.v1 = i;
			ed.v2 = p->dest;
			ed.key = p->cost;
			cp[k++] = ed;
		}
	}
	n = 0;
	for (int i = 0; i < k; i++)
	{
		if (Ae[i] == Al[i])
		{
			cp[n] = cp[i];
			Ae[n] = Ae[i];
			Al[n] = Al[i];
			n++;
		}
	}
	return true;
}